Codeforces/Codeforces Beta Round #90/D/d.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 const long long CO = 198159127;
  28
  29 const int MAXN = 1000010;
  30
  31 long long ha[MAXN], hb[MAXN], pw[MAXN];
  32 int pr[2 * MAXN];
  33
  34 int main(){
  35     string a, b;
  36     while (getline(cin, a) && getline(cin, b)) {
  37         if (a.size() != b.size()) {
  38             printf("-1 -1\n");
  39             continue;
  40         }
  41         a = " " + a;
  42         b = " " + b;
  43
  44         int n = a.size() - 1;
  45
  46         ha[0] = hb[0] = 0;
  47         pw[0] = 1;
  48         for (int i = 1; i <= n; ++i) {
  49             ha[i] = ha[i-1] * CO + (long long)a[i];
  50             //printf("ha[%d] = %lld\n", i, ha[i]);
  51             hb[i] = hb[i-1] * CO + (long long)b[i];
  52             //printf("hb[%d] = %lld\n", i, hb[i]);
  53             pw[i] = pw[i-1] * CO;
  54         }
  55
  56         string c(1 + 2*n + 1, ' ');
  57         for (int i = 1; i <= n; ++i) {
  58             c.at(i) = a.at(n-i+1);
  59         }
  60         c.at(n+1) = '$';
  61         for (int i = n + 2; i <= n + n + 1; ++i) {
  62             c.at(i) = b.at(i-n-1);
  63         }
  64         //cout << c << endl;
  65
  66         int k = 0;
  67         pr[1] = 0;
  68         for (int i = 2; i <= n + n + 1; ++i) {
  69             while ( (k > 0) and (c[i] != c[k+1]) ) k = pr[k];
  70             if (c[i] == c[k + 1]) k++;
  71             pr[i] = k;
  72         }
  73         cout << c << endl;
  74         For(i, 1, c.size()) {
  75             printf("pr[i=%d] = %d\n", i, pr[i]);
  76         }
  77
  78         int ri = -1, rj = -1;
  79         for (int i = 1; i <= n - 1; ++i) {
  80             if (a[i] != b[n-i+1]) break;
  81             int t = pr[n+1+n-i];
  82             if (t == 0) continue;
  83             int len = n-i-t;
  84             //printf("i is %d: lhs = %lld, rhs = %lld\n", i, ha[i+len] - ha[i] * pw[len],  hb[len] );
  85             if ((ha[i+len] - ha[i] * pw[len]) != hb[len]) continue;
  86             ri = i-1, rj = i + len;
  87         }
  88         printf("%d %d\n", ri, rj);
  89     }
  90     return 0;
  91 }